package leetcode.code015;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1 extends Solution015 {

	@Override
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		if (nums == null || nums.length < 3)
			return result;
		Arrays.sort(nums);
		int len = nums.length;
		int p = 0;
		while (p < len) {
			if (p > 0 && p < len && nums[p] == nums[p - 1]) {
				p++;
				continue;
			}
			List<List<Integer>> temp = twoSum(nums, p + 1, len - 1, nums[p]);
			if (temp.size() != 0)
				result.addAll(temp);
			p++;
		}
		return result;
	}

	private List<List<Integer>> twoSum(int[] nums, int x, int y, int num) {
		List<List<Integer>> result = new ArrayList<>();
		int l = x;
		int r = y;
		while (l < r) {
			if (l > x && l < r && nums[l] == nums[l - 1]) {
				l++;
				continue;
			}
			if (r < y && l < r && nums[r] == nums[r + 1]) {
				r--;
				continue;
			}
			int numl = nums[l];
			int numr = nums[r];
			if (numl + numr + num == 0) {
				List<Integer> temp = new ArrayList<>();
				temp.add(numl);
				temp.add(numr);
				temp.add(num);
				result.add(temp);
				l++;
				r--;
			} else if (numl + numr + num > 0) {
				r--;
			} else {
				l++;
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();

//		int[] array = new int[] { 0, 1, 2, 3, 3, 3, 3, 3, 4 };
//		int p = 0;
//		while (p < array.length) {
//			int now = array[p];
//			System.out.println("p>>  " + p + "now>>   " + now);
//			while (p < array.length && array[++p] == now) {
//				// p++;
//				// System.out.println("p>>>>" + p + "now>>>>" + now);
//			}
//		}

	}

}
